#include "BinarySearchTree.h"
#include <vector>
#include <random>

template<typename Comparable>
void BST_sort(std::vector<Comparable> &data);
template<typename Comparable>
void Randomized_BST_sort(std::vector<Comparable> &data);

int main(){
    int n;
    int m;

    std::cout<<"Input BST_sort function vector's length:"<<endl;
    std::cin>>n;
    std::cout<<"Input Randomized_BST_sort function vector's length:"<<endl;
    std::cin>>m;


    std::vector<int> b(n);
    for(int i=0;i<n;i++)
    b[i]=2*n-i;
    Randomized_BST_sort(b);
    std::cout<<"sort Output:"<<endl;
    for(int i=0;i<b.size();i++)
    {

        std::cout<<b[i]<<" ";
    }
    std::cout<<"\n";


    std::vector<int> c(m);
    for(int i=0;i<m;i++)
    c[i]=2*m-i;
    Randomized_BST_sort(c);
    std::cout<<"Randomized sort Output:"<<endl;
    for(int i=0;i<c.size();i++)
    {

        std::cout<<c[i]<<" ";
    }

}

template<typename Comparable>
void BST_sort(std::vector<Comparable> &data)
{
    BinarySearchTree<Comparable> A;
    vector<Comparable>* p;
    int sum=data.size();
    for(int i=0;i<data.size();i++)
    {
        A.insert(data[i]);
    }
    p=&data;
    data.clear();
    A.order(p,A.root);

}

template<typename Comparable> 
void Randomized_BST_sort(std::vector<Comparable> &data)
{
    int n=data.size();
    for(int i=1;i<n;i++)
    {
        int a=rand() % n;
        int b=rand() % n;
        Comparable digit;
        digit = data[b];
        data[b]=data[a];
        data[a]=digit;
    }
    BST_sort(data);
}
